package leetcode.每日一题;

import org.junit.Test;

import java.util.*;

/**
 * @author ：zsy
 * @date ：Created 2022/1/10 11:06
 * @description：https://leetcode-cn.com/problems/additive-number/
 */
public class 累加数 {
    @Test
    public void test() {
        Solution solution = new Solution();
        System.out.println(solution.isAdditiveNumber("199100199"));
    }

    class Solution {
        public boolean isAdditiveNumber(String num) {
            int n = num.length();
            int secondStart = 1;
            for (; secondStart < n - 1; ++secondStart) {
                if (num.charAt(0) == '0' && secondStart != 1) break;
                for (int secondEnd = secondStart; secondEnd < n - 1; secondEnd++) {
                    if (num.charAt(secondStart) == '0' && secondStart != secondEnd) break;
                    if (valid(secondStart, secondEnd, num)) {
                        return true;
                    }
                }
            }
            return false;
        }

        private boolean valid(int secondStart, int secondEnd, String num) {
            int n = num.length();
            int firstStart = 0, firstEnd = secondStart - 1;
            while (secondEnd <= n - 1) {
                String third = StringAdd(num, firstStart, firstEnd, secondStart, secondEnd);
                int thirdStart = secondEnd + 1;
                int thirdEnd = secondEnd + third.length();
                if (thirdEnd >= n || !num.substring(thirdStart, thirdEnd + 1).equals(third)) break;
                if (thirdEnd == n - 1) return true;
                firstStart = secondStart;
                firstEnd = secondEnd;
                secondStart = thirdStart;
                secondEnd = thirdEnd;
            }
            return false;
        }

        private String StringAdd(String num, int firstStart, int firstEnd, int secondStart, int secondEnd) {
            StringBuilder builder = new StringBuilder();
            int factor = 0;
            while (firstEnd >= firstStart || secondEnd >= secondStart) {
                int cur = factor;
                cur += firstEnd >= firstStart ? num.charAt(firstEnd--) - '0' : 0;
                cur += secondEnd >= secondStart ? num.charAt(secondEnd--) - '0' : 0;
                factor = cur / 10;
                cur = cur % 10;
                builder.append(cur);
            }
            if (factor != 0) {
                builder.append(factor);
            }
            return builder.reverse().toString();
        }
    }
}
